5.1 堆
堆是一种常见的数据结构，广泛应用于优先队列、排序算法（如堆排序）、内存管理等场景。
堆可以分为 最大堆 和 最小堆，堆的核心特性是 堆序性质。
即在最大堆中，任意节点的值都不小于其子节点的值，而在最小堆中，任意节点的值都不大于其子节点的值。
本节我们将介绍堆的基本概念、常见应用场景以及Go语言中的实现。
本节代码存放目录为 lesson10
概念及原理
堆 是一棵 完全二叉树，它满足以下特性：
堆序性质：
最大堆：任意节点的值不小于其子节点的值，堆顶（根节点）的值是整个堆中最大的。
最小堆：任意节点的值不大于其子节点的值，堆顶（根节点）的值是整个堆中最小的。
完全二叉树：堆是完全二叉树，意味着它的每一层节点都是满的，或者最后一层节点是从左向右填充的。
总的来说，堆的基础是二叉树，同时堆有两种类型，一种是从大到小，一种是从小到大。堆的这种特性就比较适合用来进行排序操作。
最大堆
9
/ \
5 6
/ \ /
3 4 2
节点 9 是根节点，它大于其子节点
5和6。节点 5 大于其子节点
3和4。节点 6 大于其唯一子节点
2。
最小堆
1
/ \
3 2
/ \ /
6 5 9
节点 1 是根节点，它小于其子节点
3和2。节点 3 小于其子节点
6和5。节点 2 小于其唯一子节点
9。
插入操作
插入一个新元素到堆时，需要保持堆的完全二叉树结构和堆序性质。插入步骤如下：
首先将元素插入到完全二叉树的最后一个位置。
然后通过上滤操作将新元素移动到合适的位置，以维持堆序性质。
最大堆操作示意如下所示：
1. 插入 10：
- 初始插入 10，作为堆的根节点，不需要上滤操作。
10
2. 插入 5：
- 插入 5，作为 10 的左子节点，堆序不受影响，无需上滤。
10
/
5
3. 插入 15：
- 插入 15，作为 10 的右子节点，堆序不符合最大堆的要求，需要上滤操作。
- 上滤：15 大于 10，交换它们的位置。
15
/ \
5 10
4. 插入 3：
- 插入 3，作为 5 的左子节点，堆序不受影响，无需上滤。
15
/ \
5 10
/
3
5. 插入 7：
- 插入 7，作为 5 的右子节点，堆序不符合最大堆的要求，需要上滤操作。
- 上滤：7 大于 5，交换它们的位置。
15
/ \
7 10
/ \
3 5
6. 插入 12：
- 插入 12，作为 10 的左子节点，堆序不符合最大堆的要求，需要上滤操作。
- 上滤：12 大于 10，交换它们的位置。
15
/ \
7 12
/ \ /
3 5 10
7. 插入 17：
- 插入 17，作为 12 的右子节点，堆序不符合最大堆的要求，需要上滤操作。
15
/ \
7 12
/ \ / \
3 5 10 17
- 上滤：17 大于 15，交换它们的位置，调整为：
17
/ \
7 12
/ \ / \
3 5 10 15
- 上滤：15 大于 7，交换它们的位置，调整为：
17
/ \
15 12
/ \ / \
3 5 10 7
堆的插入操作与之前学习到的AVL 树有一些类型，就是在插入时需要检查是否满足规则，如果不满足规则就进行调整。
删除堆顶元素
删除堆顶元素时，首先用堆的最后一个元素替换堆顶，然后通过下滤操作将这个元素调整到正确位置，以维持堆序性质。
操作示意如下所示：
17
/ \
15 12
/ \ / \
3 5 10 7
1. 删除 17
- 删除节点 17，将最后一个节点 7 移动到 17 的位置
7
/ \
15 12
/ \ /
3 5 10
- 此时节点 7 小于节点 15，不满足堆序规则，将 7 与 15 调换
15
/ \
7 12
/ \ /
3 5 10
2. 删除 15
- 删除节点 15，将最后一个节点 10 移动到 15 的位置
10
/ \
7 12
/ \
3 5
- 此时 节点 10 小于 节点 12，不满足堆序规则，将 12 与 10 调换
12
/ \
7 10
/ \
3 5
删除操作与插入操作其实是差不多的，只不过需要注意的是堆只能从顶部删除。
那么为什么要这样做呢？这主要是为了不破坏堆的结构，如果从任意位置都可以删除的话，那么堆序的意义就不是太大了，相当于每次删除都要重新进行排序操作。
堆的应用
堆有很多应用场景，以下是常见的几种：
优先队列：堆可以用来实现优先队列，队列中的元素按照优先级出队，堆顶元素具有最高优先级。
堆排序：堆排序是一种基于堆的数据排序算法，时间复杂度为
O(n log n)。求解 Top K 问题：使用堆可以快速找到数据集中最大的或最小的
K个元素。
Go语言的实现
接下来我们使用Go语言实现一个简单的最大堆，包括插入和删除堆顶元素的操作。
与之前实现二叉树有所不同，实现堆我们将使用数组进行，由于堆是完全二叉树，所以我们使用数组实现可以通过简单的数组索引计算父子节点关系。
例如我们有下面的堆结构：
50
/ \
30 20
/ \ / \
15 10 8 16
那么我们在数组中这样存储：
[50, 30, 20, 15, 10, 8, 16]
计算父节点我们使用公式：(i - 1) / 2
当前节点为：30
索引为：1
根据公式父节点的索引 = (1 - 1) / 2 = 0
当前节点为：20
索引为：2
根据公式父节点的索引 = (2 - 1) / 2 = 0
当前节点为：15
索引为：3
根据公式父节点的索引 = (3 - 1) / 2 = 2 / 2 = 1，也就是 30 的索引
计算子节点我们使用公式：2 * i + 1、2 * i + 2
当前节点为：30
索引为：1
根据公式左子节点的索引 = (2 * 1) + 1 = 3
根据公式右子节点的索引 = (2 * 1) + 2 = 4
实现代码如下：
// MaxHeap 定义堆结构
type MaxHeap struct {
heap []int
}
// Insert 插入新元素
func (h *MaxHeap) Insert(val int) {
h.heap = append(h.heap, val)
h.siftUp(len(h.heap) - 1)
}
// 上滤操作，维持最大堆性质
func (h *MaxHeap) siftUp(index int) {
parent := (index - 1) / 2
if parent >= 0 && h.heap[parent] < h.heap[index] {
h.heap[parent], h.heap[index] = h.heap[index], h.heap[parent]
h.siftUp(parent)
}
}
// 删除堆顶元素
func (h *MaxHeap) Remove() int {
if len(h.heap) == 0 {
return -1
}
top := h.heap[0]
h.heap[0] = h.heap[len(h.heap)-1]
h.heap = h.heap[:len(h.heap)-1]
h.siftDown(0)
return top
}
// 下滤操作，维持最大堆性质
func (h *MaxHeap) siftDown(index int) {
left := 2*index + 1
right := 2*index + 2
largest := index
if left < len(h.heap) && h.heap[left] > h.heap[largest] {
largest = left
}
if right < len(h.heap) && h.heap[right] > h.heap[largest] {
largest = right
}
if largest != index {
h.heap[index], h.heap[largest] = h.heap[largest], h.heap[index]
h.siftDown(largest)
}
}
func main() {
h := &MaxHeap{}
h.Insert(9)
h.Insert(5)
h.Insert(6)
h.Insert(2)
h.Insert(3)
h.Insert(4)
fmt.Println("堆:", h.heap)
fmt.Println("删除堆顶:", h.Remove())
fmt.Println("堆:", h.heap)
}
执行结果输出如下：
堆: [9 5 6 2 3 4]
删除堆顶: 9
堆: [6 5 4 2 3]
在上面的代码中，我们实现了一个简单的最大堆，其中 Insert 函数负责插入元素并通过上滤操作保持堆的性质，而 Remove 函数负责删除堆顶元素并通过下滤操作恢复堆序。
总结
堆是一种特殊的完全二叉树，分为最大堆和最小堆，堆的插入和删除操作通过上滤和下滤维持堆序性质
堆在实际应用中用途广泛，如优先队列、堆排序等。通过这节课的学习，我们了解了堆的基本概念、操作原理以及在Go语言中的实现。
下一节我们将继续学习优先队列的实现，它也是基于堆的应用之一。